package com.jhxy.algorithm.removeduplicates;

import java.util.BitSet;

/**
 * 用位向量/位数组，BitSet实现
 */
public class RemoveDuplicatesBitSet {

    public static void main(String[] args) {
        InputForRemoveDuplicates inputs = new InputForRemoveDuplicates("1,2,3,3,3,4,5");
        RemoveDuplicatesBitSet ins = new RemoveDuplicatesBitSet();
        int length = ins.removeDuplicates(inputs.nums);
        System.out.println(length);
        System.out.print("[");
        for (int i = 0; i < length; i++) {
            System.out.print(inputs.nums[i]);
            if (i < length - 1) {
                System.out.print(",");
            }
        }
        System.out.print("]");
    }

    private int removeDuplicates(int[] nums) {
        int retLength = 0;
        int curLength = nums.length;
        if (curLength == 0) {
            return retLength;
        }

        BitSet bitSet = new BitSet();
        //只要nums不为空，那么第一位是肯定要的
        bitSet.set(0);
        retLength = 1;

        //第一步，将数据放入到bitSet中去
        for (int i = 1; i < curLength ; i++) {
            if (nums[i] != nums[i - 1]) {
                bitSet.set(i);
                retLength++;
            }
        }

        //将不重复的元素重新放到nums数组中
        int tempIndex = curLength - 1;
        for (int i = bitSet.length() - 1; i >= 0; i--) {
            if (bitSet.get(i)) {
                nums[tempIndex] = nums[i];
                tempIndex--;
            }
        }

        System.out.println();

        for (int i = 0; i < retLength ; i++) {
            nums[i] = nums[curLength - retLength + i];
        }
        return retLength;
    }
}
